package easy

import (
	. "GoLeetcode/common"
	"math"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 简化过程,在dfs计算以每个节点为根节点的树的所有节点之和时,是可以得到以每个节点为根节点的左右子树的总和的,所以可以随带计算该根节点的坡度
func findTilt(root *TreeNode) int {
	if root == nil {
		return 0
	}

	// dfs返回以node节点为根节点的二叉树的所有节点之和
	var ans int
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		leftSum := dfs(node.Left)
		rightSum := dfs(node.Right)
		ans += int(math.Abs(float64(leftSum - rightSum)))
		return leftSum + rightSum + node.Val
	}
	dfs(root)
	return ans
}

/*
使用1带2递归,先使用一个dfs方法计算一棵树的所有节点之和,然后计算root节点左子树之和与右子树之和的差值(坡度),然后使用findTilt的左右两颗子树进行"带2"递归
时间复杂度:O(N^2)
空间复杂度:O()
*/

func findTilt1(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftSum := dfs(root.Left)
	rightSum := dfs(root.Right)
	sum := int(math.Abs(float64(leftSum - rightSum)))
	return sum + findTilt(root.Left) + findTilt(root.Right)
}

func dfs(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return node.Val + dfs(node.Left) + dfs(node.Right)
}
